import java.util.LinkedList;
import java.util.ListIterator;

public class LeetCode649 {

    public static void main(String[] args) {
        LeetCode649 leetCode649 = new LeetCode649();
        // 第一轮：DRRRRDDD
        System.out.println(leetCode649.predictPartyVictory("DRRDRDRDRDDRDRDR"));
    }

    /**
     * 思路：
     * 1.将所有人加入队列
     * 2.从队列n个人开始遍历，找到前面后面有敌人则删除敌人，然后第n+1个人开始从头开始找敌人，找到敌人则删除，没有敌人则宣告胜利
     * 3.
     * @param senate
     * @return
     */
    public String predictPartyVictory(String senate) {

        char[] arr = senate.toCharArray();
        LinkedList<Integer> RQ = new LinkedList<>();
        LinkedList<Integer> DQ = new LinkedList<>();
        int length = arr.length;

        for (int i = 0; i < arr.length; i++){
            if (arr[i] == 'D'){
                DQ.offer(i);
            }else {
                RQ.offer(i);
            }
        }

        while (!DQ.isEmpty() && !RQ.isEmpty()){
            int rIndex = RQ.poll();
            int dIndex = DQ.poll();

            if (rIndex < dIndex){
                RQ.offer(rIndex + length);
            }else {
                DQ.offer(dIndex + length);
            }
        }

        return DQ.isEmpty() ? "Radiant" : "Dire";


    }


}
